1. Field of the Invention
The present invention relates to a method, system, and article of manufacture for adjusting parameters used to prefetch data from storage into cache.
2. Description of the Related Art
Data prefetching techniques are used to prefetch data from a non-volatile storage device, such as one or more hard disk drives, to a high speed memory, such as a volatile memory device referred to as a cache, in anticipation of future data requests. The data requests may then be serviced from the high speed cache instead of the storage device which takes longer to access. In this way, data may be returned to the requesting device faster.
During a sequential read operation, an application program, such as a batch program, will process numerous data records stored at contiguous locations in the storage device. It is desirable during such sequential read operations to prefetch the sequential data into cache in anticipation of the requests from the application program. A sequential caching algorithm detects when a device is requesting data as part of a sequential access operation. Upon making such a detection, the storage controller or server may begin prefetching sequential data records following the last requested data record into cache in anticipation of future sequential accesses. The cached records may then be returned to the application performing the sequential data operations at speeds substantially faster than retrieving the records from a non-volatile storage device.
One prefetching approach is to perform a sequential readahead. In a One Block Lookahead (OBL) algorithm, one block is prefetched beyond the requested block. OBL can be of three types: (i) always prefetch—prefetch the next block on each reference, (ii) prefetch on miss—prefetch the next block only on a miss, (iii) tagged prefetch—prefetch the next block only if the referenced block is accessed for the first time. A P-Block Lookahead approach extends the idea of OBL by prefetching P blocks instead of one, where P is also referred to as the degree of prefetch. Some approaches dynamically adapt the degree of prefetch based on the workload. Other techniques have suggested a per stream scheme which selects the appropriate degree of prefetch on each miss based on a prefetch degree selector (PDS) table. In a History-based prefetching scheme, a history-based table may be used to predict the next pages to prefetch.
There are two kinds of prefetch requests: (i) synchronous prefetch, and (ii) asynchronous prefetch. A synchronous prefetch is when on a miss on page x, p extra pages are prefetched beyond page x to extend the extent of the client's read request to include more pages. An asynchronous prefetch may occur upon the occurrence of a cache hit on a page x and creates a new read request to prefetch p pages beyond those already in the cache. In each set of the p prefetched pages, a trigger page is identified at a trigger distance of g from the end of the prefetched set of pages. When g=0, the trigger is set on the last page of the prefetched set. When a trigger page is hit, an asynchronous prefetch is requested for the next set of p sequential pages. Unlike synchronous prefetching, asynchronous prefetching enables the cache to pre-store data ahead of sequential read requests for the data. Asynchronous prefetching is used in conjunction with some form of synchronous prefetching to prefetch the initial set of pages.
Sequential prefetching has a high predictive accuracy and focuses prefetching only on the sequential components of workloads. Sequential prefetching techniques include fixed synchronous (FS), adaptive synchronous (AS), and fixed asynchronous (FA). In fixed synchronous (FS) prefetching, a next page or fixed number of next pages is prefetched on a miss. In adaptive synchronous (AS) prefetching, the number of pages prefetched on every miss (p) is gradually increased as the length of the sequence referenced becomes longer. The degree of prefetch (p) starts with a small fixed number (for example, 2) and is either linearly incremented on every miss or exponentially incremented. There may be a predefined upper limit for incrementing p.
In fixed asynchronous (FA) prefetching, the degree of prefetch and trigger distance may be any fixed values.
There is a need in the art for improved techniques for prefetching data.